﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Net.Mime.MediaTypeNames;

class Sol24
{
    public ListNode Exchange2(ListNode head)//迭代不带虚拟头结点的
    {
        if (head == null || head.next == null)//head为空，或者就一个元素
        {
            return head;
        }

        ListNode next=head.next;

        head.next= next.next;
        next.next= head;

        ListNode newHead = next;
        ListNode pre = head;

       while(head.next!=null&&head.next.next != null) {//剩下的不可以为空，也不可以只剩下一个
            pre = head;
            head = head.next;
            next = head.next;
            head.next = next.next;
            next.next = head;
            pre.next = next;

        }

        return newHead;
    }

    public ListNode Exchange3(ListNode head)//迭代带虚拟头结点的，比较方便
    {
        //if (head == null || head.next == null)//head为空，或者就一个元素
        //{
        //    return head;
        //}
        ListNode dummyHead=new ListNode(-1);
        dummyHead.next = head;


        ListNode pre = dummyHead;
        ListNode next = head.next;

        while (pre.next != null && pre.next.next != null)//包含前面的null
        {//剩下的不可以为空，也不可以只剩下一个


           
            head = pre.next;
            next = head.next;


            head.next = next.next;
            next.next = head;
            pre.next = next;
            pre = head;
        }

        return dummyHead.next;
    } public ListNode Exchange(ListNode head)//递归
    {

      

        if (head.next != null && head.next.next != null)//包含前面的null
        {//剩下的不可以为空，也不可以只剩下一个


            ListNode next = head.next;

            head.next = Exchange(next.next);
            
            next.next = head;
         


            return next;
           



        }
        else{
            return head;
        }
       

       
    }
}
class Program24
{
    static void Main24(string[] args)
    {

        Sol24 sol=new Sol24();
        ListNode head = new ListNode(1);
        head.next=new ListNode(2);
        head.next.next=new ListNode(3);
        head.next.next.next=new ListNode(4);




       ListNode res=  sol.Exchange(head);
        while (res != null) {
            Console.WriteLine(res.val);
            res = res.next;
        }

        Console.ReadKey();


    }
}